home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ASME's Mechanical Engine…ing Toolkit 1997 December
/
ASME's Mechanical Engineering Toolkit 1997 December.iso
/
ai
/
algo.txt
< prev
next >
Wrap
Text File
|
1988-07-07
|
33KB
|
844 lines
Expressing Procedural Algorithms in Prolog
Michael A. Covington
Research Report 01-0012
Advanced Computational Methods Center
University of Georgia
Athens, Georgia 30602
May 26, 1986 4:25 pm
--------------------------------------------------------------
This work was supported by PACER Grant 85PCR18 from Control
Data Corporation and by Grant Number INS-85-02477 from the
National Science Foundation. The opinions expressed here are
solely those of the author. The assistance of Donald Nute and
Andre Vellino is gratefully acknowledged. Printed copies of
this and other research reports are available free on request.
--------------------------------------------------------------
With the increasing popularity of Prolog as an application
programming language, it is often necessary to develop Prolog
equivalents for algorithms that were originally expressed in
procedure-oriented languages. This paper presents a number of
strategies for doing so. I assume that the reader is already
familiar with the basic mechanisms of Prolog -- unification
(matching), backtracking, and the like.
Unless otherwise noted, the examples given here work both in full
"Edinburgh" or "DEC-10" Prolog (Clocksin and Mellish 1984) and in
Turbo Prolog (1986), which is a subset of the full language. The
examples are written in Turbo Prolog syntax, but with declarations
omitted for brevity. Full Prolog is used -- and noted as such --
when its features are needed.
The procedural interpretation of logic
Prolog is often described as a non-procedural language. In
reality, it is a semi-procedural language -- a compromise between
procedural and non-procedural programming, giving some of the
advantages of each. In a truly non-procedural language, the
programmer would provide only a logically rigorous set of
conditions that the program must fulfill; the computer would then
automatically generate an algorithm from them. Such things as the
order in which the conditions were written would have no effect.
In the interest of efficiency, Prolog contains some procedural
elements. The Prolog programmer specifies not only the rules of
inference to be used in solving a problem, but also the order in
which they are to be tried. Crucially, the programmer can even
specify that some potential paths to a solution should not be
tried at all. This makes it possible to perform efficiently many
2
computations that would be severely inefficient, or even
impossible, in pure Prolog.
The key principle of Prolog is the procedural interpretation of
logic. Consider the following Prolog rule set:
[1] in_north_america(X) :- in_usa(X).
in_usa(X) :- in_georgia(X).
in_georgia(atlanta).
This can be interpreted as a set of facts ([2] below) or as a set
of procedure definitions ([3] below).
[2] X is in North America if X is in the USA.
X is in the USA if X is in Georgia.
Atlanta is in Georgia.
[3] To prove that X is in North America,
prove that X is in the USA.
To prove that X is in the USA,
prove that X is in Georgia.
To prove that Atlanta is in Georgia,
do nothing.
The unfamiliar task of drawing inferences from data is thereby
reduced to the very familiar task of calling procedures.
In what follows I will unashamedly refer to Prolog predicate
definitions as procedures.
Conditional execution
One of the most important differences between Prolog and other
programming languages is that, in general, Prolog procedures have
multiple definitions (clauses), each applying under different
conditions. In Prolog, conditional execution is expressed, not
with if or case statements, but with these alternative definitions
of procedures.
Consider for example how we might translate into Prolog the
following Pascal procedure:
[4] procedure writename(X:integer);
begin
case X of
1: write('One');
2: write('Two');
3: write('Three')
end
end;
This is done by giving writename three definitions:
3
[5] writename(1) :- write("One").
writename(2) :- write("Two").
writename(3) :- write("Three").
Each definition matches in exactly one of the three cases. A
common mistake is to write the clauses as follows:
[6] /* bad style */
writename(X) :- X=1, write("One").
writename(X) :- X=2, write("Two").
writename(X) :- X=3, write("Three").
This gives correct results but is needlessly inefficient. It is a
waste of time to go into an inapplicable clause, perform a test
that fails, backtrack out, and try another clause, when the use of
the inapplicable clause could have been avoided in the first
place.
A key to effective programming in Prolog is making each logical
unit of the program into a separate procedure. Each if or case
statement should, in general, become a procedure call. For
example, the hypothetical Pascal procedure:
[7] procedure a(X:integer);
begin
b;
if X=0 then c else d;
e
end;
should go into Prolog as follows:
[8] a(X) :- b,
c_or_d(X),
e.
c_or_d(0) :- c.
c_or_d(X) :- X<>0, d.
This imposes a disciplined organization on the program that is
even more rigorous than the structured ("go-to-less") programming
that serves as the basis of Pascal, Ada, and C.
Guarded command sets
As Kluzniak and Szpakowicz (1985) have pointed out, Dijkstra's
"guard" concept (Dijkstra 1975) is easily expressed in Prolog. A
guarded command set is a structure of the form
4
[9] if
C1 -> A1
C2 -> A2
C3 -> A3
fi
where C1, C2, and C3 are conditions and A1, A2, and A3 are the
corresponding actions. During program execution, all the
conditions are evaluated. If all of the conditions are false, the
program terminates. Otherwise, one of the actions corresponding to
a true condition is selected for execution.
If exactly one condition is true, the guarded command set is
equivalent to an if-then or case statement. In fact, the Prolog
procedure "c_or_d" in [8] can be expressed in more Dijkstra-like
(though less efficient) form as:
[10] c_or_d(X) :- /* condition */ X=0, /* action */ c.
c_or_d(X) :- /* condition */ X<>0, /* action */ d.
Guarded command sets were developed as part of a system for
deriving algorithms from formal specifications of the problems
they must solve. In Dijkstra's system, if more than one condition
is true, no assumptions are made about which action will be taken.
In Prolog, all possible actions will be taken on successive
backtracking passes, in the order in which they are given in the
program.
The "cut" operator
Let's consider another version of "writename" ([4] above) that
includes a "catch-all" clause to deal with numbers whose names are
not given. In many extended forms of Pascal, this can be expressed
as:
[11] procedure writename(X:integer);
begin
case X of
1: write('One');
2: write('Two');
3: write('Three')
else
write('Out of range')
end
end;
One way to express this in Prolog is the following:
5
[12] writename(1) :- write("One").
writename(2) :- write("Two").
writename(3) :- write("Three").
writename(X) :- X<1, write("Out of range").
writename(X) :- X>3, write("Out of range").
This gives correct results but lacks conciseness. In order to make
sure that only one clause is applicable to each number, we have
had to add two more clauses. What we would like to say is that the
program should print "Out of range" for any number that has not
matched any of the first three clauses. We could try to express
this as follows, with some lack of success:
[13] /* incorrect */
writename(1) :- write("One").
writename(2) :- write("Two").
writename(3) :- write("Three").
writename(_) :- write("Out of range").
(Recall that the anonymous variable, written _, matches anything.)
The problem here is that the goal "writename(1)", for example,
matches both the first clause and the last clause. If a subsequent
goal fails and causes backtracking through this one, the goal
"writename(1)" will have two solutions, one that prints "One" and
one that prints "Out of range."
We want "writename" to be deterministic, that is, to give exactly
one solution for any given set of parameters, and not give
alternative solutions upon backtracking. We would therefore like
to specify somehow that if any of the first three clauses
succeeds, the computer should not try the last clause. This can be
done with the "cut" operator (written as an exclamation mark).
The cut operator commits the computer to take a particular
solution (or potential solution) without trying alternatives.
Suppose for example that we have the following rule set:
[14] b :- c, d, !, e, f.
b :- g, h.
and that the current goal is "b". If we take the first clause and
execute the cut, then it becomes impossible to look for
alternative solutions to "c" and "d" (the goals that precede the
cut in the same clause) or to "b" (the goal that invoked the
clause containing the cut). It remains possible, of course, to
backtrack all the way past "b" and look for alternatives to the
clause that caused "b" to be invoked.
What we need to do in [13] is to put a cut in each of the first
three clauses. This changes their meaning slightly, so that the
first clause (for example) says, "If the parameter is 1, then
write 'One' and do not try any other clauses."
6
[15] writename(1) :- !, write("One").
writename(2) :- !, write("Two").
writename(3) :- !, write("Three").
writename(_) :- write("Out of range").
Since "write" is deterministic, it does not matter whether the cut
is written before or after the call to "write". However, programs
are usually more readable if cuts are made as early as possible.
Making procedure calls always succeed or always fail
In order to control the flow of program execution, it is often
necessary to guarantee that a goal will always succeed regardless
of the results of the computation that it performs. Occasionally,
it is necessary to guarantee that a goal will always fail.
An easy way to make any procedure succeed is to add an additional
clause to it that succeeds with any parameters, and is tried last,
thus:
[16] f(X,Y) :- X < Y, !, write("X less than Y").
f(_,_).
A call to "f" succeeds with any parameters; it may or may not
print its message, but it will certainly not return failure and
hence will not cause backtracking in the procedure that invoked
it. Moreover, because of the cut, "f" is deterministic. The cut
prevents the second clause from being used to generate a second
solution with parameters that have already succeeded with the
first clause.
Similarly, a procedure can be guaranteed to fail by adding cut and
fail at the end of each of its definitions, thus:
[17] g(X,Y) :- X<Y, write("X less than Y"), !, fail.
g(X,Y) :- Y<X, write("Y less than X"), !, fail.
Any call to "g" ultimately returns failure for either of two
reasons: either it doesn't match any of the clauses, or it matches
one of the clauses and ends with cut and fail. The cut is written
next to last so that it won't be executed unless all the other
steps of the clause have succeeded; as a result, it is still
possible to backtrack from one clause of "g" to another.
In full Prolog, but not in Turbo Prolog, we can define procedures
"make_succeed" and "make_fail" that take a goal as a parameter,
thus:
7
[18] make_succeed(Goal) :- call(Goal), !.
make_succeed(_).
make_fail(Goal) :- call(Goal), !, fail.
In some implementations, "call(Goal)" is written simply as "Goal".
Likewise, in full Prolog but not in Turbo Prolog we can define the
procedure "once" which allows a goal to succeed exactly once, thus
making any goal deterministic:
[19] once(Goal) :- call(Goal), !.
This procedure backtracks as much as necessary to get one
successful solution to "Goal", then stops. Thus, no matter how
many possible solutions there are to "f(p)", the goal "once(f(p))"
will return only the first solution. If "f(p)" has no solutions,
"once(f(p))" fails.
Repetition through backtracking
Prolog offers two ways to perform computations repetitively:
backtracking and recursion. Of the two, recursion is by far the
more versatile. However, there are some interesting uses for
backtracking, among them the construction of "repeat-fail" loops.
In Prolog implementations that lack tail recursion elimination
(see below), "repeat-fail" looping is the only kind of iteration
that can be performed ad infinitum without causing a stack
overflow.
The predicate "repeat" is built into some Prolog implementations.
In most others, it can be defined as follows:
[20] repeat.
repeat :- repeat.
(The built-in version of "repeat" should be used if available,
since there are a few implementations in which the definition in
[20] does not prevent stack overflow.)
"Repeat" always succeeds and has an infinite number of solutions.
Thus any procedure call bracketed between "repeat" and "fail" will
be tried over and over again, even if it only generates one
solution. For instance, the following goal displays an infinite
number of asterisks:
[21] repeat, write("*"), fail.
The following Turbo Prolog procedure turns the computer into a
typewriter, accepting characters from the keyboard and displaying
them ad infinitum, until the user hits "Break" to abort the
program:
8
[22] typewriter :- repeat,
readchar(C),
write(C),
fail.
The loop can be made to terminate by allowing it to succeed
eventually, so that backtracking stops. The following version of
"typewriter" stops when the user types a carriage return (ASCII
code 13):
[23] typewriter :- repeat,
readchar(C),
write(C),
C = '\13'.
If C is equal to code 13, execution terminates; otherwise,
execution backtracks to "repeat" and proceeds forward again
through "readchar(C)" and "write(C)".
The looping in [23] can be restarted by the failure of a
subsequent goal (as in the compound goal "typewriter,fail"). To
prevent the loop from restarting unexpectedly, we need to add a
cut as follows:
[24] typewriter :- repeat,
readchar(C),
write(C),
C = '\13',
!.
In effect, this forbids looking for alternative solutions to
"typewriter."
There is a crucial difference between "repeat-fail" loops in
Prolog and repeat-until loops in Pascal. In Pascal, iteration is
always accomplished by executing all the statements in the loop,
then jumping from the end back to the beginning. In Prolog,
backtracking may cause control to jump backward from any goal to
any earlier goal that has alternative solutions. (The limiting
case is "repeat", which always has alternative solutions.)
Moreover, if any goal in a Prolog loop fails, subsequent goals
will not be attempted.
A serious limitation of "repeat-fail" loops is that there is no
convenient way to pass information from one iteration to the next.
Prolog variables lose their values upon backtracking. Thus, there
is no easy way to make a "repeat-fail" loop accumulate a count or
total. (Information can be preserved by storing it in the
knowledge base, using "assert" and "retract", but this is usually
a slow process.) With recursion, information can be transmitted
9
from one pass to the next through the parameter list. This is the
main reason for preferring recursion as a looping mechanism.
Recursion
Most programmers are familiar with recursion as a means of
implementing some very specialized, task-within-a-task algorithms
such as tree searching and Quicksort. Indeed, Prolog lends itself
well to expressing recursive algorithms developed in Lisp. What is
not generally appreciated is that any iterative algorithm can be
expressed recursively.
Here is the classic recursive algorithm for computing factorials,
expressed in Pascal and in Turbo Prolog. (Change "=" to "is" to
get standard Prolog.)
[25] function factorial(N:integer):integer;
begin
if N=0 then
factorial:=1
else
factorial:=N*factorial(N-1);
end;
[26] factorial(0,1).
factorial(N,FactN) :- N > 0,
M = N-1,
factorial(M,FactM),
FactN = N*FactM.
This is straightforward; the procedure "factorial" calls itself to
compute the factorial of the next smaller integer, then uses the
result to compute the factorial of the integer in question.
Now consider an iterative algorithm to do the same thing:
[27] function factorial(N:integer):integer;
var I,J:integer;
begin
I:=0; /* Initialize */
J:=1;
while I<N do
begin /* Loop */
I:=I+1;
J:=J*I
end;
factorial:=J /* Return result */
end;
In Pascal, this procedure does not call itself. Its Prolog
10
counterpart is a procedure that calls itself as its very last step
-- a procedure that is said to be tail recursive:
[28] factorial(N,FactN) :- fact_iter(N,FactN,0,1).
fact_iter(N,FactN,N,FactN).
fact_iter(N,FactN,I,J) :-
I < N,
NewI = I+1,
NewJ = J*NewI,
fact_iter(N,FactN,NewI,NewJ).
Here the third and fourth parameters of "fact_iter" are state
variables that pass values from one iteration to the next. State
variables in Prolog correspond to variables that change their
values repeatedly in Pascal.
Let's start by examining the recursive clause of "fact_iter". This
clause checks that I is still less than N, computes new values for
I and J, and finally calls itself with the new parameters.
The recursive call is the very last step in this clause, and in
addition, this whole clause is placed last so that, when it calls
itself, there will be no untried alternatives to be saved on the
stack. This ensures that the stack will not grow during the
iteration. (We will return to this point below.)
Because Prolog variables cannot change their values, the
additional variables NewI and NewJ have to be introduced. In
Prolog (as in arithmetic, but not in most programming languages),
the statement
X = X+1
is always false. So NewI and NewJ contain the values that will
replace I and J in the next iteration.
The first clause of "fact_iter" serves to end the iteration when
the state variables reach their final values. A more Pascal-like
but less efficient way of writing this clause would be:
[29] fact(N,FactN,I,J) :- I = N, FactN = J.
That is, if I is equal to N, then FactN (so far uninstantiated)
should be given the value of J. By writing this same clause more
concisely in [28], we make Prolog's unification mechanism do work
that would require explicit computational steps in other
languages.
Most iterative algorithms can be expressed in Prolog by following
this pattern shown here. First transform other types of loops
11
(e.g., for and repeat-until) into Pascal while loops. Then break
the computation into three stages: the initialization, the loop
itself, and any subsequent computation needed to return a result.
Express the loop as a tail recursive clause (like the second
clause of "fact_iter") with the while-condition at the beginning.
Computations to be performed after the loop terminates are placed
into another, non-recursive, clause of the same procedure, which
is set up so that it executes only after the loop is finished.
Finally, hide the whole thing behind a "front-end" procedure
("factorial" in this example) which is what the rest of the
program actually calls. The front-end procedure passes its
parameters into the tail recursive procedure along with initial
values of the state variables. The art of expressing iteration
through tail recursion is dealt with extensively, in Lisp, in the
first chapter of Abelson and Sussman (1985).
Why tail recursion is special
Whenever one Prolog procedure calls another, two things are saved
on a pushdown stack: (1) a record of what remains to be done after
return (the continuation of the calling procedure), and (2) a
record of what alternative solutions remain to be tried (the
alternative set). Normally, the continuation and the alternative
set are represented by pointers into already existing data
structures, so that it does not take any more space to represent a
large set than a small one.
Since every procedure call places information onto the stack, it
would seem that recursion would lead inevitably to stack overflow.
However, most Prolog implementations (including Turbo Prolog)
recognize a special case: if the continuation and the alternative
list are both empty, nothing need be placed on the stack. In this
case, instead of calling itself, such a procedure can simply place
new values into its parameters and jump back to the beginning of
itself. In effect, this transforms recursion into iteration.
A procedure that calls itself with an empty continuation and empty
alternative list is described as tail recursive; the process of
executing such a call without adding items to the stack is called
tail recursion elimination. (The elimination of tail recursion
does not mean that it should be banished from the program; on the
contrary, it should be used liberally because the implementation
transforms it into an efficient iterative process.)
A quick way to verify that a particular Prolog implementation
performs tail recursion elimination is to try the following
predicate:
12
[30] test(N) :- write(N),
nl,
M = N+1,
test(M).
(Again, this is Turbo Prolog syntax; change "=" to "is" to get
standard Prolog.) Start with the goal "test(1)" and see how long
execution continues. If the program runs for more than 10,000
iterations, it is a safe bet that tail recursion elimination is
taking place.
Controlling the growth of the stack
It is easy to recognize a recursive call that has an empty
continuation: the recursive call is the very last subgoal in the
clause that contains it. Determining whether the alternative set
is also empty takes somewhat more thought.
One way to get an empty alternative set is to put the recursive
call in the last clause of a predicate, as in the iterative
factorial program ([28], repeated here for convenience):
[31] factorial(N,FactN) :- fact_iter(N,FactN,0,1).
fact_iter(N,FactN,N,FactN).
fact_iter(N,FactN,I,J) :-
I < N,
NewI = I+1,
NewJ = J*NewI,
fact_iter(N,FactN,NewI,NewJ).
The recursive call only takes place when all other alternatives
have been exhausted.
The alternative set can also be made empty by using cut to rule
out alternatives, as in the following replacement for "fact_iter":
[32] fact_iter(N,FactN,I,J) :-
I < N,
NewI = I+1,
NewJ = J*NewI,
!,
fact_iter(N,FactN,NewI,NewJ).
fact_iter(N,FactN,N,FactN).
Here the recursive call occurs in the first clause, but the cut
guarantees that the second clause need not be considered as an
alternative.
13
Because "NewI = I+1" and "NewJ = J*NewI" are deterministic, the
cut can equally well be placed before them, as follows:
[33] fact_iter(N,FactN,I,J) :-
I < N,
!,
NewI = I+1,
NewJ = J*NewI,
fact_iter(N,FactN,NewI,NewJ).
fact_iter(N,FactN,N,FactN).
Note that [32] and [33] ought to be more efficient than [31]. The
first clause of [31] succeeds only on the last iteration; the rest
of the time, the first clause fails and control proceeds to the
second clause. Thus, almost every iteration must try both clauses.
In [32] and [33], the order of the clauses is reversed, so that
the first clause is the one that will almost always succeed.
Moreover, this clause contains a cut so that whenever it succeeds,
no other clause will be tried. The result is that, in [32] and
[33], only one clause -- the last one -- is tried on every
iteration except the last.
In actual tests using Turbo Prolog on an IBM PC, the times taken
to compute the factorial of 200 were 0.58 second for [31] and 0.54
second for [32] and [33]. The gain in efficiency was small because
the time saved by omitting the unnecessary test was only slightly
greater than the time needed to execute the extra cut. The gain
would have been much larger if the unnecessary clause had
contained time-consuming computations.
References
Abelson, Harold, and Sussman, Gerald Jay (1985) Structure and
Interpretation of Computer Programs. Cambridge, Massachusetts:
MIT Press.
Clocksin, W. F., and Mellish, C. S. (1984) Programming in Prolog.
Second edition. Berlin: Springer-Verlag.
Dijkstra, E. W. (1975) Guarded commands, nondeterminacy and formal
derivation of programs. Communications of the ACM 18.8:453-457.
Kluzniak, Feliks, and Szpakowicz, Stanislaw (1985) Prolog for
Programmers. London: Academic Press.
Turbo Prolog (1986) Version 1.0. Scotts Valley, California:
Borland International.
shed from the program; on the
contrary, it sho
